字符串匹配

Time Limit: 10 Sec Memory Limit: 256 MB

Description

对于一个字符集大小为C的字符串P，我们可以将任意两种字符在Р中的位置进行互换，例如P = abcba，我们交换a,b就变为bacab，交换 a, d就变为dbcbd，交换可以进行任意次。若交换后P变为了字符串Q，则我们称Q与P是匹配的。
现在给定两个字符集大小为C的字符串 S,T，请你求出S中有多少个连续子串与T是匹配的。

Input

img

Output

img

Sample Input

3 3
　　6 3
　　1 2 1 2 3 2
　　3 1 3
　　6 3
　　1 2 1 2 1 2
　　3 1 3
　　6 3
　　1 1 2 1 2 1
　　3 1 3

Sample Output

3
　　1 2 4
　　4
　　1 2 3 4
　　3
　　2 3 4

HINT

img

Solution

发现题目中颜色的具体权值是对答案无关的，然后就是只要相对位置一样即可。

那么显然是一个KMP的模型，变相更改，条件改为：两个字符上一次出现的相对位置相同（也就是位置差值相等）。

那么我们只要求出差值来KMP即可，再考虑一下串长对于答案的影响，差值>串长显然是不会影响答案的，但是直接匹配的话可能将这种情况默认为不可行，所以我们在匹配的时候判断一下串长，若dist>=当前匹配****串长则同设为0即可，更新fail的时候也要这么做。这样做KMP即可求出答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int ONE=10001;

int T,C;
int n,m;
int a[ONE],b[ONE];
int da[ONE],db[ONE],la[ONE],lb[ONE];
int fail[ONE],j;
int Ans[ONE],ans_num;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

int Da(int i,int len) {if(da[i]>=len) return 0;return da[i];}
int Db(int i,int len) {if(db[i]>=len) return 0;return db[i];}

int main()
{
    T=get();    C=get();
    while(T--)
    {
        n=get();    m=get();
        memset(la,0,sizeof(la));    memset(lb,0,sizeof(lb));
        for(int i=1;i<=n;i++) a[i]=get();
        for(int i=1;i<=m;i++) b[i]=get();

        for(int i=1;i<=n;i++) da[i]=i-la[a[i]], la[a[i]]=i;
        for(int i=1;i<=m;i++) db[i]=i-lb[b[i]], lb[b[i]]=i;

        j=0;
        for(int i=2;i<=m;i++)
        {
            j=fail[i-1];
            while(j && Db(j+1,j+1)!=Db(i,j+1)) j=fail[j];
            if(Db(j+1,j+1) == Db(i,j+1)) j++; else j=0;
            fail[i] = j;
        }

        j=0;    ans_num=0;
        for(int i=1;i<=n;i++)
        {
            while(j && Db(j+1,j+1)!=Da(i,j+1)) j=fail[j];
            if(Db(j+1,j+1) == Da(i,j+1)) j++; else j=0;
            if(j==m) Ans[++ans_num] = i-m+1, j=fail[j];

        }

        printf("%d\n",ans_num);
        for(int i=1;i<=ans_num;i++)
            printf("%d ",Ans[i]);
        printf("\n");
    }
}